1. Technical Field
The present invention relates to state machines in general and, in particular, to replicated state machines. Still more particularly, the present invention relates to a replicated state machine for providing fault-tolerant services.
2. Description of Related Art
Replicated state machines can be used to provide fault-tolerant services as described in F. B. Schneider, Implementing Fault-tolerant Services using the State Machine Approach: A Tutorial, ACM Computing Surveys, 22(4), December 1990, pp. 299-319. The above-mentioned reference defines distributed software as often being structured in terms of clients and services. Each service includes one or more server and exports operations that clients invoke by making requests. Using a single centralized server is the simplest way to implement a service; however, the resulting service can only be as fault-tolerant as the processor executing that server. Multiple servers that fail independently can be used to provide fault-tolerance service. Such is done by replicating the single server and executing the replicas on separate processors of a distributed processing system.
State machine approach refers to a method of implementing a fault-tolerant service by replicating servers and coordinating client interactions with the server replicas. With the replicated state machine approach, the service is expressed as a deterministic state machine and copies of the state machine are executed in a number of different failure domains in parallel. For example, the copies of the state machine may be executed on several different computers in parallel. Clients express their requests in terms of state machine stimuli that are committed to a sequence of such stimuli using a distributed consensus protocol. An example of a distributed consensus protocol is the PAXOS protocol as described in L. Lamport, The part-time parliament, Technical Report 49, DEC SRC, Palo Alto, 1989.
The distributed consensus protocol ensures that all state machine replicas receive the same sequence of stimuli and since, by design, they all start off with the same state and are deterministic, the state machines continue to execute as replicas of one another indefinitely. Fault-tolerance is essentially achieved because one copy of the state of the service is held by each replica so it does not matter if a subset of the replicas fail since a copy of the service state will be retained in a surviving replica.
Replicated state machines are a good way of implementing fault tolerant service, but the problem is that a client, which is making many requests, may starve other clients of access to the service completely or may increase the service time for other clients beyond what is acceptable to them. As an example, replicated state machines can be used in a storage area network (SAN). The virtualization component of a SAN provides an abstraction of the storage where the representation of a storage unit to the operating system and applications on a server is divorced from the actual physical storage where the information is contained. The virtualization component is a client of the replicated state machine services. In prior art systems, the virtualization component carries out a lot of requests that starve the other components, such as the configuration component, of request processing capability. This results in configuration request timeouts, input/output timeouts and general instability.
Consequently, it is desirable to provide an improved replicated state machine that can schedule requests from clients such that all clients can be serviced fairly.